#include "../tools.h"


class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int size = nums.size();
        vector<int> dp(size, 1);
        vector<int> cnt(size, 1);
        int res_maxlen = 1;
        int res_cnt = 1;
        for(int i = 1; i < size; ++i){
            int maxlen = 1, curlen, maxcnt=1;
            for(int j = i - 1; j >= 0; --j){
                if(nums[i] > nums[j]){
                    curlen = dp[j] + 1;
                    if(curlen > maxlen){
                        maxlen = curlen;
                        maxcnt = cnt[j];
                        continue;
                    }
                    if(curlen == maxlen){
                        maxcnt += cnt[j];
                    }
                }
            }
            dp[i] = maxlen;
            cnt[i] = maxcnt;
            if(maxlen > res_maxlen) res_maxlen = maxlen;
        }

        for(auto e: dp)
            cout << e << " ";
        cout << endl;
        for(auto e: cnt)
            cout << e << " ";
        cout << endl;

        int res = 0;
        for(int i = 0; i < size; ++i){
            if(dp[i] == res_maxlen) res += cnt[i];
        }

        return res;
        
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;

    vector<int> nums = {1,2,4,3,5,4,7,2};
    cout << sol.findNumberOfLIS(nums);

    return 0;
}
